package main

func main() {

}

func longestPalindrome(s string) string {
	begin, end := 0, 0
	dp := make([]bool, len(s))

	for i := 0; i < len(s); i++ {
		for j := 0; j <= i; j++ {
			if j == i {
				dp[j] = true
			} else if j+1 == i {
				dp[j] = s[j] == s[i]
			} else {
				if s[j] == s[i] {
					dp[j] = dp[j+1]
				} else {
					dp[j] = false
				}
			}
			if dp[j] && i-j > end-begin {
				begin, end = j, i
			}
		}
	}
	return s[begin : end+1]
}
